# Сложность алгоритмов BIG 0
## Введение 

Алгоритмы сортировки и поиска — важный класс алгоритмов. 

Они могут использоваться как самостоятельно, так и в качестве основы для более сложных алгоритмов, о которых мы поговорим в следующих главах. 

Мы познакомимся с различными типами алгоритмов сортировки, сравним их производительность при различных подходах к разработке; затем подробно рассмотрим несколько алгоритмов поиска. 

Наконец, мы разберем изученные алгоритмы на практическом примере. 

Вы должны научится оценивать сильные и слабые стороны различных алгоритмов сортировки и поиска. 

Такие алгоритмы — основа для большинства более сложных алгоритмов. Знакомство с ними поможет вам понять современные сложные алгоритмы.


## Понятие сложности алгоритма

```python
def palindrom_1(string):
    ...

def palindrom_2(string):  ...


def palindrom_3(string):
   ...

```


Все 3 функции делаю одно и тоже 
> НАГАН, А РОЗА УПАЛА


Есть ли разница?

Все 3 работают. Задача выбрать какой мы будем использовать в нашем приложении.

В одном случае строка состоит из 5 символов, во втором из тысячи или миллиона.

Конечно, мы можем использовать  возможности модуля timeit

```python
start_time = timeit.default_timer()
for i in range(10):
    palindrom_1(s)
print(timeit.default_timer() - start_time)

start_time = timeit.default_timer()
for i in range(1000):
    palindrom_2(s)
print(timeit.default_timer() - start_time)

start_time = timeit.default_timer()
for i in range(1000):
    palindrom_3(s)
print(timeit.default_timer() - start_time)

start_time = timeit.default_timer()
for i in range(1000):
    palindrom_4(s)
print(timeit.default_timer() - start_time)

```

Результат:

```
0.00010520004434511065
0.0005378000205382705
0.001941199996508658
0.000548599986359477

```

И предположить, что 1 и 4 функция отработает быстрее.

 Чуть позже вернемся к этим функциям
Начнем с простого:

Как посчитать сумму капитализацию банковского вклада:
```
Гражданин 1 января открыл счет в банке, вложив 1000 руб. Каждый год размер вклада увеличивается на 5% от имеющейся суммы. 

Определить сумму вклада через n лет (n - целое положительное число, вводимое с клавиатуры). 
```

```python
def capitalization_1(deposit, persent, year):
    ...
    return deposit


def capitalization_2(deposit, persent, year):
  ...
   return deposit

res1 = capitalization_1(1000, 5, 5)
print(res1)


res2 = capitalization_2(1000, 5, 5)
print(res2)
```

Обе функции считаю капитализацию вклада. 

Вопрос тот же самый. Какой алгоритм  выбрать? 
Почему? Попробуем это замерить.

Импортируем из модуля timeit класс Timer

Синтаксис следующий

```python
t = Timer("function_name(10)", "from __main__ import function_name")

# в таймере формируем запрос к функции. 
# А с помощью timeit вызываем функцию заданное количество раз.

t.timeit(number=1)


```

Начинаем исследовать

```python
t = Timer("capitalization_1(1000, 5, 5)", "from __main__ import capitalization_1")
print(f'{t.timeit(number=10):.6f}')

t = Timer("capitalization_2(1000, 5, 5)", "from __main__ import capitalization_2")
print(f'{t.timeit(number=10):.6f}')

```

Результат:
```
0.000085
0.000034
```

Увеличим кол-во вызовов до 10^7
```
6.508492
2.954078
```

При увеличение n – время увеличивается, причем линейно!


### Ещё пример

Вирус каждые 3 часа делится на 2 новых вируса. 
Определить, сколько вирусов будет через n часов 

Входные данные:
1, 11
Выходные данные:
8


```python
def counter_virus_1(n, t):
    ...
    return n


def counter_virus_2(n, t):
    ...
    return n 


t = Timer("counter_virus_1(2, 100)", "from __main__ import counter_virus_1")
print(f'{t.timeit(number=10 ** 6):.6f}')

t = Timer("counter_virus_2(2, 100)", "from __main__ import counter_virus_2")
print(f'{t.timeit(number=10 ** 6):.6f}')

```

Результат
```
2.139690
0.311525
```

Разниц почти на порядок.

Но разницы часто достигают тысячи порядков

```python
def sum_one(n):
    sum = 0 #1 -присваивание
    for i in range(1, n + 1):
        sum += i # n-присваиваний
    return sum


def sum_two(n):
    sum = (n * (n + 1)) / 2
    return sum
```
Обе функции считаю сумму последовательности. 

Итого: сложность равна `1 + n`

Но нам не все операции интересны. 

Нам интересна доминирующая часть функции, которая перекрывает все остальное. 

Если представить, что у вас есть премия 100 рублей при зарплате в `1000 рублей` – это неплохо. 
У при зарплате в `100_000` р. вы её не заметите. 

Т.е. мы учитываем только доминирующую часть. 

В нашем случае это n.

Порядок этой величины называют `big O`. 

Таким образом сложность этого алгоритма О(n)

А теперь посмотрим на вторую функцию

```python
def sum_two(n):
    sum = (n * (n + 1)) / 2
    return sum
```

то, мы увидим, что всегда у нас выполняется одна операция. 

### Сложность O(1).

Гениально. 

Всегда нужно стремится к такой эффективности. 

Уходить от переборных методов.

Изучать жадные алгоритмы, динамику.

`O(1)` никогда не зависит от количества входных данных.
Даже если мы для второго алгоритма будем иметь такую формулу:

> 100 + n**2 + 25

Учитывать ли числа 100 и 25. 

Конечно если n = 1, то да. 

Но по мере увеличения n нам они погоду не делают и мы оставляем доминирующую часть. 

Всё равно сложность останется `O(1)`.

Хрестоматийно, каждый алгоритм имеет свой худший, лучший и средний случай.

К примеру, мне нужно ехать из точки `А` в точку `B`. 

Можно доехать без пробок за `30 мин`, а с пробками `45 мин`, а можно вообще не доехать, или приехать в место окончательной регистрации граждан.

Технически сложность алгоритма может быть любой, хоть `n` в кубе.
Но очень часто в `99%` - случаем нам попадутся вот такие сложности

![](img/img-01.png)


O(1) – константа, линия уходит вертикально вверх, t -константа. Они редки.
1)	Константая сложность
2)	Логарифмическая (логарифм n)
3)	Линейная
4)	Линейно-логарифмическая
5)	Квадратичная, кубическая
6)	Экспоненциальная (2**n)
7)	Факториальная

Чем ниже чем ужаснее.

Но на малых `n` – разницы нет. 

Факториал уходит в бесконечность.

# Пример факториальной сложности


```python
from itertools import *
from string import ascii_uppercase as ABC

x = list(product('abcde', repeat=5))
y = list(permutations(ABC, 26))

print(len(x))
print(len(y))


```

Учимся дальше это дело использовать.

Ниже пример задачи, который выполняется с какой-то скоростью (временем). 

Мы видим, что правильный алгоритм способен на 15 порядков работать быстрее, а при малых n разницу мы не видим.


![](img/img-02.png)

Важно уметь не только определять сложность алгоритма, но и его рассчитывать.

Посмотрим на абстрактный пример:

```python
def test(n):
    a = 1
    b = 2
    c =3 
    for i in range(n):
        for j in range(n):
            a = i * i
            b = j * j
            c = i * j
    x = 4
    y = 5
    for i in range(n):
        x = a * b + 42
        y = c * i
    z = 100
```

> 3 + 3n**2 + 2 + 2n + 1

1)	Находим 3 присваивания
2)	Далее еще 3 присваивания в цикле, который находится еще в одном цикле
А цикл в цикле – это квадрат O(n2). Значит эта часть дает 3n**2
3)	Далее снова 2 присваивания (+2)
4)	Далее снова 2 шага в обычном цикле 2n 
Таким образом размер задания
> 
(n) = 3 + 3n**2 + 2 + 2n + 1

Это промежуточный шаг. 
А из него мы считаем сложность. 

Но по определенным правилам (математики) 

> 3 + 3n**2 + 2 + 2n + 1 = 3n**2 + 2n + 6

И опять, константы можно проигнорировать, остается 

> 3n**2 + 2n

Дальше оставляем доминирующую часть: 

> 3n**2

Ну и 3 несущественна, при большом n
Таким образом получаем:
> T(n) = O(n**2)

Обратите внимание, что это всего лишь концепт.
Вы должны уметь визуально вычленять самую сложную доминирующую часть

```
1)	count += 1 # O(1)
2)	цикл for, while # O(n)
3)	цикл в цикле О(n**2)
```	

Два примера:


```python
def pow_one(base, exp):
    result = 1
    while exp > 0:
        result *= base
        exp -= 1
    return result

```


```python
def pow_two(base, exp):
    result = 1
    while exp > 0:
        if exp % 2 == 0:
            base *= base
            exp //= 2
        else:
            result *= base
            exp -= 1
    return result

```

А теперь подумайте, проанализируйте, что делают эти функции. 
Вторя в 2 раза больше, но работает гораздо быстрее. 


Мини практикум:
6 заданий
Какова сложность следующих алгоритмов?

```python
# 1

def one(array):
    result = 0;
    for i in array:
        for j in array:
            result += i * j
    return result

# 2

def two(array):
    result = 0
    for i in array:
        result += 1
    for j in array:
        result -= 1
    return result

# 3
def three(n):
    i = 0
    while n > 0:
        i += 2
        n //= 2
    return i

# 4
def four(n):
    for i in range(n):
        j = 0
        cnt = 50 * n # если поменять на n **2 то O(n**3)
        sum = 0
        while j < cnt:
            j += 1
            sum += 1
    return sum

# 5
def five(n):
    for i in range(n):
        while i % 2 != 0: # банальный if
            print(i)
            i -= 1
        print("Done")

# 6
def six(n):
    for i in range(n):
        cnt = n * n
        for j in range(cnt):
            if j == 4:
                return -1
            print("Done")

```
